package primaryAlgorithm.shuffleArray;

import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * @Date 2020/03/24
 * @author 王光浩
 * @Thinking 创建一个新数组，是原数组的一份拷贝，这个数组用于打乱原数组。
 * @Analysis 时间复杂度:未知（在足够倒霉的情况的下），空间复杂度O（n）
 */
public class Solution {
	private int[] orginal;
	private int[] shuffl;
	public Solution(int[] nums) {
		orginal=nums;
		shuffl=new int[nums.length];
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
    	return orginal;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
    	Random tem=new Random();
    	int next=0;
    	int count=0;
    	Set<Integer> set=new HashSet<Integer>(); //防止重复加入
    	while(count<orginal.length) {
    		int index=tem.nextInt(orginal.length);
    		if(!set.contains(index)) {
    			shuffl[next++]=orginal[index];
    			count++;
    			set.add(index);
    		}
    	}
    	return shuffl;
    }
}
